#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 102. 二叉树的层序遍历.py
@time: 2022/1/6 16:29
@desc: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
> 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

@解题思路：
    1. bfs
    2. Ot(n), Os(n)
'''
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        res, queue, temp = [], [], []
        queue.append([root])
        while queue:
            lvl = queue.pop(0)
            temp = []
            next_lvl = []
            while lvl:
                node = lvl.pop(0)
                temp.append(node.val)
                if node.left:
                    next_lvl.append(node.left)
                if node.right:
                    next_lvl.append(node.right)
            if next_lvl:
                queue.append(next_lvl)
            res.append(temp)


        return res

if __name__ == '__main__':
    root = TreeNode(3, left=TreeNode(9), right=TreeNode(20, left=TreeNode(15), right=TreeNode(7)))
    res = Solution().levelOrder(root)
    print(res)